package com.cn.codebrush.动态规划;

import java.util.Arrays;

/**
 * @Author Boolean
 * @Date 2022/5/15 18:42
 * @Version 1.0
 */
public class No416分割等和子集 {
    public static void main(String[] args) {
        int[] nums = {1,5,11,5};
        int[] nums1 = {1,2,3,5};
        int[] nums2 = {2,2,6};
        System.out.println(canPartition(nums2));
    }

    /**
     * 01背包问题
     * @param nums
     * @return
     */
    public static boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        if(sum % 2 != 0) return false;//整数相加不可能得小数
        int W = sum / 2;//相当于背包总承重
        int [] dp = new int[W+1];  //dp[i]  表示实现i 的情况有几种，w+1 是为了与w和数组下标对应
        dp[0] = 1;  //实现0 的情况有一种
        for (int num : nums) {
            for (int i = W; i >= num; i--) {  //01背包 问题 特色，从后往前
                dp[i] += dp[i-num];
            }
        }
        return dp[W] != 0;
    }

}
